//这里记一下哈希表的笔记
//就是把符号表看成数组，用哈希函数，转换key成为数组的索引
//issue：1.哈希函数 2.相等检验 3.冲突解决
//所有java类都内置了hashcode（）这一方法，会返回一个32位的int值，如果他们相等，那么他们的hashcode也相等
//自己实现hashcode，先从一个很小的质数开始，将hash=hash*31+valule.hashcode(),对每个数据项都进行这种操作，如果是null，返回0，如果是数组，需要对里面的每一项都进行这样的处理
//我们要保证符号表的每个key对应的哈希值都是等概率的
//对应到数组中，通常把哈希值模数组大小得到数组的索引
//为避免hashcode得到负值，可以将其&0x7fffffff
//可以用邻接表来解决冲突问题，就是数组的每个元素都是一个list,这种方法，数组大小通常是数据总量的五分之一
//另一种方法是线性探测，这种方法的话数组大小就必须大于数据总量了，最好是一倍
//如果是一些很重要的场合，需要确保程序按想法执行，那最好用红黑树而不是哈希以保证程序运行
//如果用的是java发布的hashcode，那么可能会导致网络安全风险
public class Hash <Key,Value>{
    int M=1000;
    private Key[] keys=(Key[]) new Object[M];
    private Value[] values=(Value[]) new Object[M];
    public int hashcode(String a[])
    {
        int hash=17;
        for(int i=0;i<a.length;i++)
        hash=hash*31+a.hashCode();
        return hash;
    }

    private int hash(Key key)
    {
       return key.hashCode()&0x7fffffff%M;
    }

    //这里实现一下线性探测
    public void Put(Key key,Value value)
    {
        int i=0;
        for(i=hash(key);keys[i]!=null;i=(i+1)%M)
        {
            if(keys[i].equals(key))
            {
                break;
            }
        }
        keys[i]=key;
        values[i]=value;
    }

    public Value Get(Key key)
    {
        int i=0;
        for(i=hash(key);keys[i]!=null;i=(i+1)%M)
        {
            if(keys[i].equals(key))
            {
                return values[i];
            }
        }
        return null;
    }

   
    public static void main(String[] args){

        System.out.println("Hello, World!");
    }
}
